package 面试刷题.小米;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * dfs模板题
 * https://www.nowcoder.com/practice/987f2981769048abaf6180ed63266bb2?tpId=196&tqId=39583&ru=/exam/oj
 */
public class ch02_单词搜索 {

    char[][] board;
    char[] word;
    boolean[][] vis;
    int[][] move = {
            {1, 0},
            {-1, 0},
            {0, 1},
            {0, -1},
    };

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param board string字符串一维数组
     * @param word  string字符串
     * @return bool布尔型
     */
    public boolean exist(String[] board, String word) {
        this.board = new char[board.length][];
        for (int i = 0; i < this.board.length; i++) {
            this.board[i] = board[i].toCharArray();
        }
        return exist(this.board, word);
    }

    public boolean exist(char[][] board, String word) {
        vis = new boolean[board.length][board[0].length];
        this.board = board;
        this.word = word.toCharArray();
        List<int[]> starts = new ArrayList<>();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (board[i][j] == this.word[0]) {
                    starts.add(new int[]{i, j});
                }
            }
        }
        for (int[] start : starts) {
            if (dfs(start[0], start[1], 0)) {
                return true;
            }
        }
        return false;
    }

    public boolean dfs(int x, int y, int cur) {
        if (cur == word.length - 1) return true;
        vis[x][y] = true;
        for (int[] mv : move) {
            int nx = mv[0] + x;
            int ny = mv[1] + y;
            if (nx >= 0 &&
                    ny >= 0 &&
                    nx < board.length &&
                    ny < board[0].length &&
                    !vis[nx][ny] &&
                    board[nx][ny] == word[cur + 1]) {
                if (dfs(nx, ny, cur + 1)) {
                    return true;
                }
            }
        }
        vis[x][y] = false;
        return false;
    }

    @Test
    public void t1() {
        String[] bs = {"CAA", "AAA", "BCD"};
        System.out.println(exist(bs, "AAB"));
        System.out.println(exist(bs, "SEE"));
        System.out.println(exist(bs, "XYZY"));
    }

}
